There are many kinds of animation tools which enable the user, either an experienced animator or a novice, to define an object or objects and to provide motion to that object. An exemplary tool is the Flash tool, commercially available from Adobe of the USA. With this tool, the animator may create an animated character and may generate an animated movie or video sequence using the character.
US patent publication 2005/0063596 describes a method of animation using images of objects. The publication also describes a semi-automatic tool for cutting an object out of an image. The object can then be used in the animation. The tool allows a user to draw a border line around an object to be cut out from a picture. Based on a comparison of a segment of a border line drawn by the user and characteristic lines in the image, the tool suggests one or more possible continuation paths for the line segment. Optionally, in at least some cases, the tool suggests a plurality of paths, so that the user may choose the most suitable path. If one of the suggested paths follows the border line desired by the user, the user may select that path and the tool automatically fills in an additional segment of the border line, responsive to the selection.
The method described in US 2005/0063596 is an example of template matching, which is one term for the fitting of a model (template) to empirical data (signal). In template matching, a template is matched to an object of an image. The book, Active Contours, by Andrew Blake, et al., and the article Active Shape Models—Their Training and Application (Cootes, etc., Computer Vision and Image Understanding, Vol. 61, No. 1, January, pp. 38-59, 1995) both discuss various other types of template matching.
Template matching, as with other fitting operations, is a minimization, with respect to the model parameters, of the discrepancy between the actual measurements and the model approximation. According to the structure of the model used (linear or non-linear in the parameters), the corresponding optimization problem appears as a linear or a non-linear one.
There are many difficult problems that appear in a practical implementation of template matching. Some of them arise both in linear and non-linear cases, other are specific for the non-linear regression.
1. Noisy Data. One of the main difficulties in any template matching is presented by the noise in the empirical data (signal). In some problems, the noise may be much stronger in amplitude than the original signal, while in others, the noise may corrupt “geometrically significant” parts of the data.
2. Matching efficiency. Application of the standard minimization methods may be computationally problematic. Even in a linear case, in the presence of noise, such methods may run for a long (and unpredictable) amount of time. This is especially true for non-linear problems. In many practical problems (in particular, in image analysis), this makes template matching infeasible.
3. Ill-Posed Matching. Many important problems in template matching lead to a certain degeneracy. In particular, the minimization of the discrepancy between the actual measurements and the model approximation, with respect to the model parameters, may turn out to be highly degenerate. The standard minimization methods usually fail in such situations.
4. “Dimension course”: The number of essential control parameters of a typical medium-quality human template is at least 30. A non-linear minimization in this dimension range may be prohibitively inefficient.